#include <stdio.h>

#define MAX_LEN 1000

// 优势：seg_tree每个节点都记录了不同的数组区间和，构造线段树和查询区间和的时间复杂度为O(logn)
// 缺点：可以单点更新，但不适用于存在数组添加删除的情况。


// 构造线段树
// tree[0] 记录arr[start, end]区间的和
// tree[1] 左节点记录arr[start, mid]区间的和
// tree[2] 右节点记录arr[mid+1, end]区间的和
void build_seg_tree(int arr[], int tree[], int node, int start, int end) {
	if (start == end) {
		tree[node] = arr[start];
	} else {
		int mid = (start + end) / 2;
		int left_node = 2 * node + 1;
		int right_node = 2 * node + 2;
		
		build_seg_tree(arr, tree, left_node, start, mid);
		build_seg_tree(arr, tree, right_node, mid+1, end);
		tree[node] = tree[left_node] + tree[right_node];
	}
}

// 将arr[idx]修改为val，然后更新线段树
void update_seg_tree(int arr[], int tree[], int node, int start, int end, int idx, int val) {
	if (start == end) {	// 找到arr[idx]对应的tree[node]
		arr[idx] = val;
		tree[node] = val;
	} else {	// 判断arr[idx]落在哪个分支
		int mid = (start + end) / 2;
		int left_node  = 2 * node + 1;
		int right_node = 2 * node + 2;
		
		if (idx >= start && idx <= mid)
			update_seg_tree(arr, tree, left_node, start, mid, idx, val);
		else 
			update_seg_tree(arr, tree, right_node, mid+1, end, idx, val);
		tree[node] = tree[left_node] + tree[right_node];
	}
}

// 查询数组[L, R]区间的和
int query_seg_tree(int arr[], int tree[], int node, int start, int end, int L, int R) {
	// printf("%d - %d\n", start, end); // 显示递归情况

	if (L > end || R < start) 
		return 0;
	else if (L == R || (L <= start && end <= R)) // 当前[start, end]被包含在[L, R]中
		return tree[node];
	else {	// 如查询arr[2, 5]，要分割成arr[2] + arr[3, 5]
		int mid = (start + end) / 2;
		int left_node  = 2 * node + 1;
		int right_node = 2 * node + 2;
		int left_sum  = query_seg_tree(arr, tree, left_node, start, mid, L, R);
		int right_sum = query_seg_tree(arr, tree, right_node, mid+1, end, L, R);
		return (left_sum + right_sum);
	}
}

int main()
{
	int arr[] = {1, 3, 5, 7, 9, 11};	
	int size = 6;
	int tree[MAX_LEN] = {0};
	build_seg_tree(arr, tree, 0, 0, size-1);
	// 构造的线段树为36 9 27 4 5 16 11 1 3 0 0 7 9 0 0 
	// update arr[4] = 6, seg_tree[]: 33 9 24 4 5 13 11 1 3 0 0 7 6 0 0
	printf("seg_tree[]: ");
	for (int i = 0; i < 15; i++) {
		printf("%d ",tree[i]);
	}
	printf("\n");

	printf("update arr[4] = 6, seg_tree[]: ");
	update_seg_tree(arr, tree, 0, 0, size-1, 4, 6);
	for (int i = 0; i < 15; i++) {
		printf("%d ",tree[i]);
	}
	printf("\n");

	printf("sum of arr[2, 5] = %d\n", query_seg_tree(arr, tree, 0, 0, size-1, 2, 5));

	return 0;
}